package 题目集.动态规划.背包问题;

import java.util.Arrays;
import java.util.OptionalDouble;

import org.junit.Test;

/**
 * 凑成目标和的方案数。https://leetcode.cn/problems/target-sum/description/
 * 存在负数的动态规划(范围平移) dp[i][j]:i个选择，凑成j的方案数
 * dp[i][j]=dp[i-1][j-nums[i]]+dp[i-1][j+nums[i]]
 */
public class ch03_目标和_位置偏移 {
	int pos = 1001;
	int[] nums;

	/**
	 * sum的值域为 target-sum[0..n-1]到target+sum[0..n-1];
	 */
//	public int dfs(int i, int sum) {
//		if (i == 0) {
//			return sum == 0 ? 1 : 0;
//		}
//		int add = dfs(i - 1, sum + nums[i - 1]);
//		int sub = dfs(i - 1, sum - nums[i - 1]);
//		return add + sub;
//	}
//	public int findTargetSumWays(int[] nums, int target) {
//		this.nums=nums;
//		return dfs(nums.length,target);
//	}
	/**
	 * todo：为什么只用平移到sum，不需要平移到sum+target
	 */
	public int findTargetSumWays(int[] nums, int target) {
		int sum = Arrays.stream(nums).sum();
		if (target > sum || target < -sum) {
			return 0;
		}
		int n = nums.length;
		int[][] dp = new int[n + 1][sum * 2 + 1];
		dp[0][sum] = 1;
		for (int i = 1; i <= n; i++) {
			for (int j = -sum; j <= sum; j++) {
				if (j - nums[i - 1] + sum >= 0) { // +sum是偏移量
					dp[i][j + sum] += dp[i - 1][j - nums[i - 1] + sum];
				}
				if (j + nums[i - 1] + sum <= 2 * sum) {
					dp[i][j + sum] += dp[i - 1][j + nums[i - 1] + sum];
				}
			}
		}
		return dp[n][sum + target];
	}

	// 垃圾eclipse，@Test注解巨他妈难用，蓝桥杯是真他妈没妈
	@Test
	public void test() {
		int[] arr = { 1000 };
		int t = -1000;
		int res = findTargetSumWays(arr, t);
		System.out.println(res);
	}
}
